package com.example.hot100;

import com.example.tree.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个二叉树，检查它是否是镜像对称的。
 *
 *  例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *      1
 *     / \
 *    2   2
 *   / \ / \
 *  3  4 4  3
 *
 *  但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 *      1
 *     / \
 *    2   2
 *     \   \
 *     3    3
 */
public class Leetcode101_IsSymmetric {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(3);

        System.out.println(new Solution().isSymmetric(root));

    }

    static class Solution {
        /**
         * 两个指针分别向左向右移动，然后判断值是否相等
         * 递归方式
         * @param root
         * @return
         */
        public boolean isSymmetric2(TreeNode root) {
            if (root == null) return true;
            return check(root.left, root.right);

        }

        private boolean check(TreeNode node1, TreeNode node2) {
            if (node1 == null && node2 == null) return true;
            if (node1 == null || node2 == null) return false;

            return node1.val == node2.val
                    && check(node1.left, node2.right)
                    && check(node1.right, node2.left);
        }

        /**
         * 迭代实现
         * @param root
         * @return
         */
        public boolean isSymmetric1(TreeNode root) {
            if (root == null) return true;
            TreeNode node1, node2;
            Deque<TreeNode> queue = new LinkedList<>();

            // 初始化队列
            queue.offer(root.left);
            queue.offer(root.right);

            while (!queue.isEmpty()) {
                node1 = queue.poll();
                node2 = queue.poll();

                if (node1 == null && node2 == null) continue;
                if ((node1 ==null || node2 == null) || node1.val != node2.val) {
                    return false;
                }

                queue.offer(node1.left);
                queue.offer(node2.right);

                queue.offer(node1.right);
                queue.offer(node2.left);
            }
            return true;
        }

        public boolean isSymmetric(TreeNode root) {
            return isSymmetric2(root);
        }
    }
}
